package pers.qianyu.month_202012.date_20201209;

import java.util.*;

/**
 * [Leetcode 每日一题]
 * 62. 不同路径
 * https://leetcode-cn.com/problems/unique-paths/
 *
 * @author mizzle rain
 * @date 2020-12-09 14:01
 */
public class UniquePaths {
    /**
     * 动态规划解法
     */
    public int uniquePaths(int m, int n) {
        //dp[i][j] 表示 从起始位置 移动到位置 i，j 有几种移动方法
        int[][] dp = new int[m][n];
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = 1;
        }
        Arrays.fill(dp[0], 1);
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }

    /**
     * 数学解法
     * [leetcode 评论区 @xzt]：
     * 机器人一定会走m+n-2步，即从m+n-2中挑出m-1步向下走不就行了吗？即C(m+n-2,m-1)。
     */
    public int uniquePaths2(int m, int n) {
        long ans = 1;
        for (int x = n, y = 1; y < m; ++x, ++y) {
            ans = ans * x / y;
        }
        return (int) ans;
    }

    /**
     * 数学解法
     */
    public int uniquePaths3(int m, int n) {
        int a = m + n - 2;
        int b = m - 1;
        // 等于求 C(a, b)
        long res = 1;
        for (int i = 1; i <= b; i++) {
            res = res * (i + a - b) / i;
        }
        return (int) res;
    }
}
